\subsection{Definition and framework}
\label{sec:intervention-framework}
All three areas of our research on intervention strategies
(centralized intervention strategy, decentralized intervention
strategy, behavior changes) have a common model framework. Thus, we
briefly present the framework first, and then state our results and
proposed research in subsequent sections.

Let $V$ denote the set of users/individuals/computers (henceforth,
referred to as {\em nodes}). Let $G=(V,E)$ denote the underlying
contact graph over $V$; an edge $e=(u,v)\in E$ indicates that the
diffusion can spread from $u$ to $v$. We let $p(e)$ or $p(u,v)$ denote
the probability that diffusion spread from node $u$ to node $v$. For
$S\subset V$, we let $G\sqb{S}$ denote the subgraph of $G$ induced by
set $S$. We assume infection is initiated at a node chosen from $V$
according to some arbitrary probability distribution. Let $w_v$ denote
the probability that node $v$ is chosen as the initial infection
point, and let $w(S)=\sum_{v\in S}w_v$ for $S\subset V$. In most of
this proposal, we use the SIR model for epidemics, in which each
infected node $u$ infects each susceptible neighbor $v$ independently
with probability $p(u,v)$ (see \cite{durrett06,newman:spread02,Ne03}
for additional information). But, our framework and associated
questions are relevant for a broader class of diffusion
processes. Nodes which are successfully vaccinated are assumed not to
spread the infection. An important aspect of our framework is that
interventions, like vaccines, are only partially efficacious, and
succeed only with probability $p_s$. However, nodes do not know
whether the intervention has succeeded, and might alter their
behaviors.

The strategy for each node $v$ consists of two decisions:
\begin{enumerate}
\item Whether to adopt an intervention, such as vaccination or
  quarantine (modeled node deletion). Let $a_v\in \sqb{0,1}$ denote
  the probability that node $v$ gets vaccinated. Let $\vec{a}$ denote
  the strategy vector for all nodes. We need the notation of {\em
    attack graph}, denoted by $G_{\vec{a}}$, which is the subgraph of
  $G$ in which each node is deleted with probability $a_v$
  \cite{AspnesCY2006}.
\item Behavioral changes that alter connections: such behavior changes
  could happen in many ways, and we abstract it by considering
  $p_b(u,v)$, which denotes the modified transmission probability on
  edge $(u,v)$. While the behavior changes can be manifested as fairly
  general vectors $\vec{p_b}$, we focus on an important special case
  where these changes occur only when applied interventions. We
  consider two specific models. In the {\em 1-sided model}, vertex $u$
  after vaccination (if failed) increases the transmission probability
  to $p_b$ on all incident edges $(u,v)$, while in the {\em 2-sided
    model}, vertex $u$ after vaccination (if failed) increases the
  transmission probability only on edges $(u,v)$ for which vertex $v$
  is also vaccinated.
\end{enumerate}

The rationale behind the behavioral change models is that after
vaccination, it makes sense for an individual to take advantage of the
social contact network to enhance their economic value.  We formalize
this aspect below.  The 1- and 2-sided models signify two potential
ways in which the contagion spread could be affected: whether it
requires increased contact from any one endpoint, or both endpoints.
There are a number of natural hybrid models that we will also consider
in our study.  Since increased contact comes with increased risks, we
sometimes refer to this behavior change as ``risky behavior''.

The information used by nodes is an important aspect of the decision
making process, and we quantify this in terms of a parameter $d$,
which denotes the maximum number of hops to which a node can get
information about infections and/or vaccinations. Now we consider a
generalized non-cooperative game formulation $\mathcal{G}(G,d)$ by
defining individual costs, which involve the following components: (i)
$C_v$ denotes the cost of node $v$ getting vaccinated.  We assume this
is independent of the disease dynamics; (ii) $B_v$ denotes the
``benefit'' of increased contact (e.g., in the form of information and
centrality of the node in the social organization); and (iii) $L_v$
denotes the cost for node $v$ resulting from an infection. We assume
that node $v$ only has information about the graph within its
$d$-neighborhood; let $p_v(\vec{a},\vec{p_b},d)$ denote the
probability that node $v$ becomes infected, given the decision vectors
$\vec{a}$ and $\vec{p_b}$. Then, the cost to node $v$ is defined as
\begin{eqnarray}
\cost_v\left(\bar{a},\vec{p_b},d\right) = C_v a_v + B_v p_b(v) +(1-a_v)L_v\cdot p_v\left(\bar{a},\vec{p_b},d\right).\label{eqn:cost}
\end{eqnarray}

A Nash equilibrium \cite{nash51} (henceforth, NE) is a strategy vector
$\vec{a}$ such that no node $v$ has any incentive to switch his
strategy, if all other nodes' strategies are fixed. In most of the
proposal, we focus on pure NE. We consider variants in which the term
$p_v(\vec{a},\vec{p_b},d)$ using only partial information about the
graph and individual decisions within the $d$-neighborhood; as we
discuss later, information has a significant impact on the dynamics
and structure of NE in these games.  \junk{Another related notion is that of
Stackelberg strategies \cite{roughgarden:sicomp04}, where we assume an
administrator can control the strategy vectors $(\vec{a_S},
\vec{p_{b,S}})$ of a subset $S\subset V$ of the nodes, while the
remaining nodes in $V-S$ choose strategy vectors $(\vec{a_{V-S}},
\vec{p_{b,V-S}})$.  These pairs $(\vec{a_S}, \vec{p_{b,S}})$ and
$(\vec{a_{V-S}}, \vec{p_{b,V-S}})$ together form a Stackelberg
strategy vector. This allows the administrator to control the kinds of
equilibria that are achieved.}

The total social cost of a strategy profile is the sum of the
individual costs, which is $\cost\left(\bar{a}, \vec{p_b},d\right) =
\sum_{v=1}^n \cost_v\left(\bar{a}, \vec{p_b},d\right)$.  A socially
optimal strategy is a pair of vectors $\vec{a}, \vec{p_b}$ that
minimizes this cost - this is not necessarily (and is not usually) a
pure NE. Therefore, the cost of a pure NE relative to the social cost
is an important measure; the maximum of this ratio (i.e., over all
possible pure NE) is also known as the \emph{price of
  anarchy}~\cite{koutsoupias99worst}.

